home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / sa / a_queue < prev    next >
Text File  |  1996-06-01  |  5KB  |  151 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- a_queue.sa: Array based queue
  3. -- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
  4. -- Copyright (C) 1995, International Computer Science Institute
  5. -- $Id: a_queue.sa,v 1.4 1996/06/01 21:36:09 gomes Exp $
  6. --
  7. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  8. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  9. -- LICENSE contained in the file: Sather/Doc/License of the
  10. -- Sather distribution. The license is also available from ICSI,
  11. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  12. -------------------------------------------------------------------
  13.  
  14. class QUEUE{T} < $QUEUE{T} is include A_QUEUE{T}; end;
  15. -------------------------------------------------------------------
  16. class A_QUEUE{T} < $QUEUE{T} is
  17.    -- An array-based queue that expands using amortized doubling.
  18.    include COMPARE{T};
  19.    
  20.    private attr buf: ARRAY{T};
  21.    private attr head: INT;    -- Index of head
  22.    private attr tail: INT;    -- Index of next insert
  23.  
  24.    --              ------ Initialization/Duplication ------
  25.    create: SAME is
  26.       return(create_capacity(1));
  27.    end;
  28.  
  29.    create(a: $ELT{T}): SAME is
  30.       -- Create from an ordered container of elements "a"
  31.       -- Insert all the elements in "a" into the queue
  32.       -- such that the last element of "a" will also be the last
  33.       -- element of the queue
  34.       res ::= #SAME;
  35.       loop res.enq(a.elt!) end;
  36.       return res;
  37.    end;
  38.  
  39.    create_from(a: ARRAY{T}): SAME is
  40.       -- Create from elements of the array "a". Convenient to
  41.       -- specify the queue using an array literal as argument
  42.       return #SAME(a);
  43.    end;
  44.    
  45.    create_capacity(allocate: INT): SAME is
  46.       -- Create, allocating for "allocate" elements. Can grow later
  47.       return(new.build(allocate));
  48.    end;
  49.  
  50.    copy: SAME is
  51.       res ::= #SAME(self);
  52.       return res;
  53.    end;
  54.         
  55.    private build(sz: INT): SAME is
  56.       buf := #(sz);
  57.       head := 0;
  58.       tail := 0;
  59.       return(self);
  60.    end;
  61.    
  62.    --              ------ Insertion/Removal --------------- 
  63.    enq(e: T) pre ~void(self) is
  64.       -- Enqueue the element "e" into the tail of the queue
  65.       if ((tail+1).mod(buf.size) = head) then 
  66.      -- #OUT+"Doubling queue\n";
  67.      -- Queue is full, need to expand the buffer
  68.      r: ARRAY{T} := #ARRAY{T}(2*buf.size);
  69.      -- Copy from the head to the end of the original buffer
  70.      i ::= head; loop until!(i = buf.size);        
  71.         r[i] := buf[i];
  72.         i := i + 1;
  73.      end;
  74.      -- Copy the wrap around portion (which must fit, due to the doubling)
  75.      if (tail < head) then
  76.         dest ::= buf.size;
  77.         i := 0; loop until!(i = tail);
  78.            r[dest] := buf[i];
  79.            i := i + 1;
  80.            dest := dest + 1;
  81.         end;
  82.         tail := buf.size+tail;
  83.      end;
  84.      buf := r;
  85.       end;
  86.       -- New insertion position
  87.       buf[tail] := e;
  88.       tail := (tail+1).mod(buf.size);
  89.    end;
  90.    
  91.    remove: T pre ~is_empty is
  92.       -- Error if the queue is empty
  93.       res ::= buf[head];      
  94.       -- erik: Invalidate the pointer, for the sake of the gc.
  95.       -- (could be omitted for value types)
  96.       buf[head] := void;
  97.       head := (head+1).mod(buf.size);
  98.       return(res)
  99.    end;
  100.  
  101.    --              ------ Access/Measurement --------------
  102.    current: T is return top end;
  103.       
  104.    top: T pre ~is_empty is
  105.       -- Return the top most elemetn of the queue
  106.       return(buf[head]);
  107.    end;
  108.  
  109.    size: INT is 
  110.       -- Return the number of elements in the queue
  111.       if (tail >= head) then return(tail - head) 
  112.       else return((buf.size-head)+tail); end;
  113.    end;
  114.    
  115.    --              ------ Queries/Comparison --------------
  116.    is_empty: BOOL pre ~void(self) is return(head=tail) end;
  117.    
  118.    has(el: T): BOOL is 
  119.       loop e ::= elt!; if elt_eq(e,el) then return true end; end;
  120.       return false;
  121.    end;
  122.       
  123.    --              ------ Cursor --------------------------
  124.    elt!: T pre ~void(self) is
  125.       -- Return the elements in the queue in their normal order without
  126.       -- changing the queue. Starts with the head of the queue 
  127.       -- and works downward
  128.       if (head = tail) then quit; end;
  129.       i ::= head;
  130.       loop until!(i = tail);
  131.      yield(buf[i]);
  132.      i := (i + 1).mod(buf.size);
  133.       end;
  134.    end;
  135.       
  136.    str: STR pre ~void(self) is
  137.       res ::="";
  138.       res := res+"["+head+","+tail+","+buf.size+"]";
  139.       loop 
  140.      f ::= elt!;
  141.          fstr: STR;
  142.      typecase f
  143.      when $STR then    fstr := f.str else fstr := "?" end;
  144.          res := res+",".separate!(fstr);
  145.       end;
  146.       return(res);
  147.    end;
  148.  
  149. end; -- class QUEUE
  150. -------------------------------------------------------------------
  151.